문제 https://www.acmicpc.net/problem/2616문제기차는 맨 앞에 있는 기관차 1대가 손님이 탄 객차 여러 칸을 끌고 간다. 기관차가 고장나면 기차를 운행할 수 없게 되므로 최근 철도청은 기관차 고장에 대비하여 몇몇 역에 소형 기관차 3대를 배치하기로 결정하였다. 소형 기관차는 평소에 이용하는 기관차보다 훨씬 적은 수의 객차만을 끌 수 있다.기관차가 고장났을 때 끌고 가던 객차 모두를 소형 기관차 3대가 나누어 끌 수 없기 때문에, 소형 기관차들이 어떤 객차들을 끌고 가는 것이 좋을까하는 문제를 고민하다가 다음과 같이 하기로 결정하였다.소형 기관차가 최대로 끌 수 있는 객차의 수를 미리 정해 놓고, 그보다 많은 수의 객차를 절대로 끌게 하지 않는다. 3대의 소형 기관차가 최대로 끌..
전체 글
항공대 알고리즘 동아리 Koala 🥰문제문제그룹 단어란 단어에 존재하는 모든 문자에 대해서, 각 문자가 연속해서 나타나는 경우만을 말한다. 예를 들면, ccazzzzbb는 c, a, z, b가 모두 연속해서 나타나고, kin도 k, i, n이 연속해서 나타나기 때문에 그룹 단어이지만, aabbbccb는 b가 떨어져서 나타나기 때문에 그룹 단어가 아니다.단어 N개를 입력으로 받아 그룹 단어의 개수를 출력하는 프로그램을 작성하시오.입력첫째 줄에 단어의 개수 N이 들어온다. N은 100보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 단어가 들어온다. 단어는 알파벳 소문자로만 되어있고 중복되지 않으며, 길이는 최대 100이다.출력첫째 줄에 그룹 단어의 개수를 출력한다.예제 입력 1 복사3happynewyear예제 출력 1 복사3예제 입력 ..
문제https://www.acmicpc.net/problem/17951알고리즘매개변수탐색풀이구간을 나눌 기준을 매개변수로 두고, 그 기준보다 커지면 그룹으로 나누는 방식으로 진행하면 된다.그룹의 개수가 많다면 기준치를 높여서 줄이는 방향으로, 적다면 기준치를 낮춰서 늘리는 방향으로 진행한다 생각하면 조금 편하다.코드inf=10**10def solve(): n,k=map(int,input().split()) arr=list(map(int,input().split())) ans=parametric_search(n,k,arr) print(ans)def parametric_search(n,k,arr): mn=0 mx=inf ans=0 while mn=k: ..
https://www.acmicpc.net/problem/12847 for문을 두 번 돌려야해서 이게 맞나? 싶었으나생각해보니 o(n)이라 그냥 돌렸다.def main(): n, m = map(int,input().split()) trr = list(map(int,input().split())) prefixsum = trr.copy() for i in range(1, n): prefixsum[i] += prefixsum[i-1] maxx = prefixsum[m-1] for i in range(m, n): maxx = max(prefixsum[i]-prefixsum[i-m], maxx) print(maxx)if __name__..
https://www.acmicpc.net/problem/8911 기초적인 시뮬레이션 문제이다. 이동했을 때 가장 작은 x, y값과 가장 큰 x, y값을 기억했다가 크기를 구하면 된다.이처럼 x, y의 상하좌우 배열을 만들어놓고 상태에 따라 인덱스를 바꿔끼는 풀이는 자주 보이니 기억해둬야겠다.dx = [-1,0,1,0]dy = [0,-1,0,1]def control(s,x,y,dir): if s == 'F': x += dx[dir] y += dy[dir] return dir, x, y elif s == 'B': x -= dx[dir] y -= dy[dir] ..
문제https://www.acmicpc.net/problem/7453알고리즘투 포인터 or 해시 맵, 중간에서 만나기풀이a,b,c,d로 4중 for문을 돌리면 O(N^4)의 경우 시간초과로 터진다.이걸 a,b와 c,d로 나눠서 각각 O(N^2)으로 해결하고, 분리된 ab와 cd를 해시맵 또는 투포인터로 연결시켜주면, O(N^2)으로 문제를 해결할 수 있다.해시맵보다는 투포인터를 추천한다. 해시맵에 값이 너무 들어가는 경우 해시 충돌로 인해 속도가 오히려 느려진다.코드from sys import stdininput = stdin.readlinen = int(input())A, B, C, D = [], [], [], []for _ in range(n): a, b, c, d = map(int, input..
문제 문제알파벳 대문자로 구성되어있는 문자열 S가 주어졌을 때, S에 등장하지 않는 알파벳 대문자의 아스키 코드 값의 합을 구하는 프로그램을 작성하시오.문자열 S가 “ABCDEFGHIJKLMNOPQRSTUVW” 일 때, S에 등장하지 않는 알파벳 대문자는 X, Y, Z이다. X의 아스키 코드 값은 88, Y는 89, Z는 90이므로 이 아스키 코드 값의 합은 267이다.알파벳 대문자의 아스키 코드 값은 다음과 같다.ABCDEFGHIJKLMNOPQRSTUVWXYZ6566676869707172737475767778798081828384858687888990입력입력은 T개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에는 입력 데이터의 수를 나타내는 정수 T가 주어진다. 각 테스트 데이터는 한 줄로 구성되어..
문제 https://www.acmicpc.net/problem/5218길이가 같은 두 단어가 주어졌을 때, 각 단어에 포함된 모든 글자의 알파벳 거리를 구하는 프로그램을 작성하시오.두 글자 x와 y 사이의 알파벳 거리를 구하려면, 먼저 각 알파벳에 숫자를 할당해야 한다. 'A'=1, 'B' = 2, ..., 'Z' = 26. 그 다음 y ≥ x인 경우에는 y-x, y 예를 들어, 'B'와 'D' 사이의 거리는 4 - 2 = 2이고, 'D'와 'B' 사이의 거리는 (2+26) - 4 = 24이다.입력 첫째 줄에 테스트 케이스의 수 (출력 각 테스트 케이스 마다 각 글자의 알파벳 거리를 공백으로 구분해 출력한다. Algorithm1. 두 알파벳을 입력받는다.2. 두 알파벳의 아스키코드를 빼 거리를 구한다. ..
문제https://www.acmicpc.net/problem/2688문제어떤 숫자가 줄어들지 않는다는 것은 그 숫자의 각 자리 수보다 그 왼쪽 자리 수가 작거나 같을 때 이다.예를 들어, 1234는 줄어들지 않는다. 줄어들지 않는 4자리 수를 예를 들어 보면 0011, 1111, 1112, 1122, 2223이 있다. 줄어들지 않는 4자리수는 총 715개가 있다.이 문제에서는 숫자의 앞에 0(leading zero)이 있어도 된다. 0000, 0001, 0002는 올바른 줄어들지 않는 4자리수이다.n이 주어졌을 때, 줄어들지 않는 n자리 수의 개수를 구하는 프로그램을 작성하시오.입력첫째 줄에 테스트 케이스의 개수 T(1 출력각 테스트 케이스에 대해 한 줄에 하나씩 줄어들지 않는 n자리 수의 개수를 출력한..
문제문제알파벳 소문자로만 이루어진 단어 S가 주어진다. 각 알파벳이 단어에 몇 개가 포함되어 있는지 구하는 프로그램을 작성하시오.입력첫째 줄에 단어 S가 주어진다. 단어의 길이는 100을 넘지 않으며, 알파벳 소문자로만 이루어져 있다.출력단어에 포함되어 있는 a의 개수, b의 개수, …, z의 개수를 공백으로 구분해서 출력한다.예제 입력 1 복사baekjoon예제 출력 1 복사1 1 0 0 1 0 0 0 0 1 1 0 0 1 2 0 0 0 0 0 0 0 0 0 0 0 https://www.acmicpc.net/problem/10808 Algorithm1.사용자로 부터 소문자로만 이루어진 단어 s를 입력받는다.2.알파벳 소문자의 아스키코드를 이용하여 아스키코드를 하나씩 늘려가며 모든 알파벳의 개수를 파악할..
문제 https://www.acmicpc.net/problem/10867문제N개의 정수가 주어진다. 이때, N개의 정수를 오름차순으로 정렬하는 프로그램을 작성하시오. 같은 정수는 한 번만 출력한다. 입력 첫째 줄에 수의 개수 N (1 ≤ N ≤ 100,000)이 주어진다. 둘째에는 숫자가 주어진다. 이 수는 절댓값이 1,000보다 작거나 같은 정수이다. 출력 첫째 줄에 수를 오름차순으로 정렬한 결과를 출력한다. 이때, 같은 수는 한 번만 출력한다. Algorithm1. 정수를 리스트로 입력받는다2. 수의 중복을 막기 위해 리스트를 set으로 바꿨다 다시 리스트로 바꿔준다3. 리스트에 sort를 써서 정렬시킨뒤 출력한다 Codeimport sysN = int(sys.stdin.readline())..
https://www.acmicpc.net/problem/15724 전형적인 누적합 문제라 이게 왜 DP에 있지? 하는 고민이 들었습니다찾아보니 이런 식의 누적합 풀이법도 사실 DP 테이블을 사용하고 채우므로, 넓은 의미에서 DP 풀이가 맞다고 하더라구요! import sysinput = sys.stdin.readline def main(): n,m = map(int,input().split()) ground = [] for _ in range(n): ground.append(list(map(int,input().split()))) prefixSum = [[0 for i in range(m+1)] for j in range(n+1)] for i in ran..